package com.my.collection.graph.v1;

import java.util.*;

/**
 * Created by ZhongGang
 * at 2018/10/12 10:05
 * <p>
 * V代表顶点，基于HashMap和HashSet实现的邻接表无向图
 */
public class Graph<V> {
    private Map<V, Set<V>> table = new HashMap<>();

    /**
     * 添加顶点
     *
     * @param v
     */
    public void addVertex(V v) {
        if (v == null) {
            throw new NullPointerException();
        }

        if (this.table.containsKey(v)) {
            throw new ElementExistException();
        }

        this.table.put(v, new HashSet<>());
    }

    /**
     * 连接两个顶点
     *
     * @param from
     * @param to
     */
    public void addEdge(V from, V to) {
        if ((!this.table.containsKey(from)) || (!this.table.containsKey(to))) {
            throw new ElementNotFoundException();
        }

        //无向图在构造两个顶点的边时，要同时在各顶点的邻接表中加入对方
        this.table.get(from).add(to);
        this.table.get(to).add(from);
    }

    /**
     * 从某个给定顶点开始出发对图进行深度遍历
     * <p>
     * 伪代码：
     * 构造一个空的栈，一个空的遍历列表，将给定顶点推入栈
     * 循环判断栈是否为空，不为空进入循环
     * 弹出栈顶元素放入列表，并将顶点标记为遍历过，将顶点的所有未被标记过遍历的邻接顶点压入栈
     * 返回遍历数组
     *
     * @param v
     * @return
     */
    public List<V> dfs(V v) {
        if (!this.table.containsKey(v)) {
            throw new ElementNotFoundException();
        }

        Stack<V> stack = new Stack<>();
        List<V> visited = new ArrayList<>();
        stack.push(v);
        while (!stack.isEmpty()) {
            V pop = stack.pop();
            if (!visited.contains(pop)) {
                visited.add(pop);
            }

            Set<V> vs = this.table.get(pop);
            for (V element : vs) {
                if (!visited.contains(element)) {
                    stack.push(element);
                }
            }
        }

        return visited;
    }

    /**
     * 深度遍历 递归版本
     *
     * @param visited
     * @param v
     */
    private void dfs(List<V> visited, V v) {
        visited.add(v);

        Set<V> vs = this.table.get(v);
        for (V v1 : vs) {
            if (!visited.contains(v1)) {
                dfs(visited, v1);
            }
        }
    }

    /**
     * 从某个给定顶点开始出发对图进行广度遍历
     * <p>
     * 伪代码：
     * 构造一个空的队列，一个空的遍历列表，将给定顶点从队列尾部入队
     * 循环判断队列是否为空，不为空进入循环
     * 从队列头部出队元素放入列表，并将顶点标记为遍历过，将顶点的所有未被标记过遍历的邻接顶点进行入队操作
     * 返回遍历数组
     *
     * @param v
     * @return
     */
    public List<V> bfs(V v) {
        if (!this.table.containsKey(v)) {
            throw new ElementNotFoundException();
        }

        Queue<V> queue = new Queue<>();
        List<V> visited = new ArrayList<>();
        queue.enq(v);
        while (!queue.isEmpty()) {
            V deq = queue.deq();
            if (!visited.contains(deq)) {
                visited.add(deq);
            }

            Set<V> vs = this.table.get(deq);
            for (V element : vs) {
                if (!visited.contains(element)) {
                    queue.enq(element);
                }
            }
        }

        return visited;
    }

    /**
     * 找出从出发顶点到目的顶点间的所有连通路径
     *
     * @param from
     * @param to
     * @return
     */
    public List<List<V>> paths(V from, V to) {
        throw new UnsupportedOperationException();
    }

    /**
     * 找出从出发顶点到目的顶点间的最短连通路径
     *
     * @param from
     * @param to
     * @return
     */
    public List<V> theShortestPath(V from, V to) {
        throw new UnsupportedOperationException();
    }
}
